CrackMe« Practices for Newbies - Algorithm Analysis

CrackMe^« Practices for Newbies ~ Moderated

Algorithm Analysis - The 4011C1 routine
Friday, 29-Jan-99 19:42:36
212.211.14.143 writes:

Installment 5:

Notes on the algorithms.

This time I'll just look at the routine at 4011c1. The end of this routine is easiest to deal with first. I have dumped it here, it's only a few lines:

004011F4 add esi, 14h ; next we'll be checking the answer
004011F7 add edi, 8
004011FA mov ecx, 3
004011FF check_3_dwords: ; CODE XREF: sub_4011C1+4C j
004011FF lodsd
00401200 mov ebx, [edi]
00401202 add edi, 4
00401205 cmp eax, ebx
00401207 jnz short wrong_file
.....nops cut out......
0040120D loop check_3_dwords
0040120F mov eax, 1 ; this is where we want to be
00401214 retn
00401215 wrong_file: ; CODE XREF: sub_4011C1+46 j
00401215 xor eax, eax
00401217 retn

The important points are the return value of eax, this is the value which is compared straight after calling this routine. It directly determines whether the code from string2 is correct, against what should be the username. That's all it does and so let's take a look at the first part. (Note if we know what we want, eg 'CRONOS' then we can reverse to the start of this routine very easily, we want string2='CRONOS' at that point.

OK, now in reverse order (heh), here is the first part of this routine:

004011C1 sub_4011C1 proc near ; CODE XREF: sub_401000+9D p
004011C1 xor eax, eax
004011C3 xor ebx, ebx
004011C5 mov esi, offset string1secondha
004011CA mov edi, offset cracked_by_name
004011CF mov ebp, [edi+0Ch] ; from first string - zero in my reg
004011D2 and ebp, 0FFFFFFh
004011D8 shl ebp, 8 ; still zero in mine
004011DB xor ebp, 55555555h ; now 55555555h
004011E1 mov ecx, 3 ; encrypt 3 dwords
004011E6 loc_4011E6: ; CODE XREF: sub_4011C1+31 j
004011E6 std ; this really sucks
004011E7 lodsd
004011E8 add eax, ebp
004011EA mov ebx, [edi]
004011EC mul ebx ; the awkward multiply
004011EE mov eax, edx ; takes the high part, not the low!
004011F0 cld ; can't reverse everything here
004011F1 stosd
004011F2 loop loc_4011E6 ; loops around

This is more complex. It is basically the second part of the encryption routine. The first part was the lossy shifter (to be discussed yet). This is the first part. Notice that if string1 is all zeroes (as mine is in my keyfile) then the value of ebp is straightforward and is 55555555h. Now this is used to multiply the encrypted string2, and the MSB is used to carry forward. (Actually as a side note - it would have been much better to use the LSB in this algorithm for two reasons. Firstly it would always be reversible given it is not divisible by 2 (relatively prime to 2 to the power 32). Secondly it is actually much harder to reverse, unless you are a mathematician and happen to notice that 3*55555555h is congruent to -1 mod 2 to the power 32).

Anyway the result of all of this is that you cannot always reverse this multiply. This may require some considerable messing about with string1 to find a valid input, and then it becomes questionable as to whether a valid key generator always exists.

To this point the reversal is a straight divide (which is how I tracked my name back to a keyfile). We know what the output is at the bottom of this part (our name), and we just trace it back up, which basically means undoing this multiply (if you can).

Later we will see some further problems in the funny shifter....!!!!

Cronos.

Cronos